1. Field of the Invention
The present invention relates generally to garbage collection in a computer system, and in particular to garbage collection concurrent with mutator execution.
2. Description of the Related Art
As object-based systems become widespread, the need for systems supporting a large number of objects is increasing. As processor speeds rise, these object stores need to provide fast access to large collections of repeatedly used objects so that system throughput is not interrupted. FIG. 1 illustrates an example of a typical memory hierarchy for a conventional object-based system. The system includes a processor 10, which is connected to an object cache 12. The object cache 12 is connected to a translator 14, which is connected to main memory 16.
The object cache 12 is a form of fast memory holding recently accessed objects. A cache line in the object cache 12 generally contains part of an object or a whole object. When the objects in the object cache 12 are no longer accessible, they are typically reclaimed through a process known as garbage collection.
Garbage collection is the systematic reclamation of allocated memory of objects when these objects are no longer used by an executing program. To reclaim an allocated piece of memory, a garbage collector first identifies and marks all the reachable objects as “live”. Live objects are those objects which may be reached from a root object or reference, and a root object is always deemed live.
One of the drawbacks of such a process is that in most cases the system is required to stop or pause the executing applications during garbage collection. An executing application program is generally referred to as a mutator and the application work is generally performed by mutator threads. At any given time there may be many mutator threads executing applications. Thus pausing the mutator threads during garbage collection may significantly decrease the performance of the system.
One solution to this problem has been to perform garbage collection concurrently with the mutator's execution of the application program. However, another problem arises when garbage collection is performed simultaneously with the mutator threads' execution of application programs. The mutator threads may create new objects or update memory references while the garbage collection is in progress. There exists a risk that the in-cache garbage collector may miss marking live objects and the live objects may then be subsequently reclaimed by the garbage collector.
FIG. 2 illustrates how an in-cache garbage collector (ICGC) might miss a live object during concurrent garbage collection. FIG. 2 shows six cache lines 20, 22, 24, 26, 30 and 32 having six objects, root “r”, “a”, “b”, “c”, “d”, and “e” respectively with allocated memory. The cache lines have two bits associated with them: a mark bit 29 and a non-local bit 27. A root object is an object that is always deemed live and it differs from other objects because it has a non-local bit 27 set as indicated by the shaded non-local bit. A garbage collector starts at cache line 20 having the root object and traces all pointers from the root object and marks all objects encountered as live. In FIG. 2, object “a” and “b” are all marked as live as indicated by mark bit 27. However, when the ICGC scans cache line 24 it will not see any other object being referenced by object “b”. Therefore, it will return to cache line 22. While the GC was scanning cache line 24 the mutator deleted the reference from object “a” to object “c” as shown by arrow 28. Subsequently, when the ICGC returns to cache line 22, the mutator thread adds a reference from object “b” to object “c” as indicated by the dotted arrow 23. Since the ICGC did not see the reference “c” while it was scanning the cache line 24; the ICGC will assume that object “c” is garbage and the memory allocated to object “c” would be subsequently reclaimed along with objects d and e. Obviously, the subsequent reclamation of the allocated memory of object “c” by the ICGC is a problem.
In view of the foregoing there is a need for an object-based system that conducts garbage collection and mutator execution with minimal mutator pauses, and further, there is a need for concurrent garbage collection and mutator execution without the erroneous reclamation of memory allocated to live objects.